package main

import "fmt"

func main() {
	nums := []int{3, 5, 1, 2, 7, 6, 9}
	sortNums := quickSort(nums, 0, len(nums)-1)
	for _, v := range sortNums {
		fmt.Println(v)
	}
}

//快速排序 ：单边循环
func quickSort(nums []int, startIndex, endIndex int) []int {
	if startIndex >= endIndex {
		return nums
	}
	//确认下一次基准索引
	pivotIndex := partitionTwoSide(nums, startIndex, endIndex)
	//通过递归实现 根据基准元素索引，分成左右两部分排序
	quickSort(nums, startIndex, pivotIndex-1)
	quickSort(nums, pivotIndex+1, endIndex)
	return nums
}

//partition 单边循环 分治处理
//nums:待交换的元素
//startIndex:开始下标
//endIndex:结束下标
func partitionOneSide(nums []int, startIndex, endIndex int) int {
	//取开始索引为基准元素
	pivot := nums[startIndex]
	//标记索引默认为开始索引
	markIndex := startIndex

	for i := startIndex + 1; i <= endIndex; i++ {
		if nums[i] < pivot {
			//如果有比基准元素小的，则将标记+1，随后交换标记位置元素与当前小于基准元素的元素
			markIndex++
			nums[i], nums[markIndex] = nums[markIndex], nums[i]
		}
	}

	nums[startIndex] = nums[markIndex]
	nums[markIndex] = pivot
	//返回标记索引作为下一次的基准元素索引
	return markIndex
}

//partitionTwoSide 双边循环
func partitionTwoSide(nums []int, startIndex, endIndex int) int {
	pivot := nums[startIndex]
	//左侧指针为开始索引
	leftIndex := startIndex
	//右侧指针为结束索引
	rightIndex := endIndex

	//左右指针未重合前，一直比较
	for leftIndex != rightIndex {
		//右侧元素大于基准值，则左移
		for leftIndex < rightIndex && nums[rightIndex] > pivot {
			rightIndex--
		}
		//左侧元素小于等于基准值，则右移
		for leftIndex < rightIndex && nums[leftIndex] <= pivot {
			leftIndex++
		}
		//当右侧元素小于等于基准值 且 左侧元素大于基准值
		if leftIndex < rightIndex {
			//交换左右2个元素
			nums[leftIndex], nums[rightIndex] = nums[rightIndex], nums[leftIndex]
		}
	}

	//将pivot基准值与left与right的重合点进行交换
	nums[startIndex] = nums[leftIndex]
	nums[leftIndex] = pivot

	return leftIndex
}
